package 差分Plus离散化;

import daythree.Tree;
import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/5/30 21:26
 */
public class 美团流星差分solution {


    /*
     因为 值域 很大， 所以 这里采用 离散化 + 差分
       https://leetcode.cn/circle/discuss/VbYrF4/

     */

    // 因为 值域 很小， 这里 没有使用 离散化， 也能过， 但是 真正的 笔试过程中， 是过不了的！
    public static void main0(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = Integer.valueOf(sc.nextLine());
        int[] st = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::new).toArray();
        int[] et = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::new).toArray();

        int max = Arrays.stream(et).max().getAsInt();


        //  diff
        int diff[] = new int[max + 2];
        for (int i = 0; i < n; i++) {
            diff[st[i]] += 1;
            diff[et[i] + 1] -= 1;
        }
        int ans = 0, count = 0, sum = 0;
        for (int i = 1; i < diff.length; i++) {
            sum += diff[i];
            if (ans == sum) {
                count++;
            } else if (ans < sum) {
                ans = sum;
                count = 1;
            }
        }
        System.out.println(ans + " " + count);
//        return new int []{ans,count};
    }


    public static void main2(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        TreeMap<Integer, Integer> diff = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int key = sc.nextInt();
            diff.put(key, diff.getOrDefault(key, 0) + 1);
        }
        for (int i = 0; i < n; i++) {
            int key = sc.nextInt() + 1;
            diff.put(key, diff.getOrDefault(key, 0) - 1);
        }
        // 思路是错的
//        int ans = 0, count = 0, sum = 0 , pre = 0;
//        for(Map.Entry<Integer,Integer> entry : diff.entrySet()){
//            sum += entry.getValue();
//            if(ans == sum ){
//                count += pre == 0 ? 1 : entry.getKey() - pre + 1;
//            }else if(ans < sum){
//                count = 1;
//                ans = sum;
//            }
//            pre = entry.getKey();
//        }
        int ans = 0, sum = 0, count = 0;
        /*
        这里非常的细节， 离散化差分 求前缀和 的这种思想！
         */
        List<int[]> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : diff.entrySet()) {
            sum += entry.getValue();
            ans = Math.max(ans, sum);
            list.add(new int[]{entry.getKey(), sum});
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i)[1] == ans) {  //   注意 这里的 i + 1 ，根本就不用考虑 越界 ， 这就是一个 非常巧妙的一个点， ** 有起点 ，必有终点！ ** 所以这样写，肯定是正确的！
                count += list.get(i + 1)[0] - list.get(i)[0];
            }
        }
        System.out.println(ans + " " + count);
    }

    @Test
    public void test() {

    }


    public void slove(int nums[][]) {
        int max, min;
        max = min = nums[0][0];
        for (int num[] : nums) {
            min = Math.min(min, num[0]);
            max = Math.max(max, num[1]);
        }

        // diff arr
        int diff[] = new int[max + 2];

        for (int num[] : nums) {
            diff[num[0]]++;
            diff[num[1] + 1]--;

        }

        int MAX = Arrays.stream(diff).max().getAsInt();
        int count = 0, sum = 0;
        for (int i = 0; i < diff.length; i++) {
            sum += diff[i];
            if (sum == MAX) {
                count++;
            }
        }
        System.out.println(count + " " + MAX);
    }

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = Integer.valueOf(sc.nextLine());
        int[] st = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::new).toArray();
        int[] et = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::new).toArray();

        int max = Arrays.stream(et).max().getAsInt();


        //  diff
        int diff[] = new int[max + 2];
        for (int i = 0; i < n; i++) {
            diff[st[i]] += 1;
            diff[et[i] + 1] -= 1;
        }

        int count = 0, sum = 0, MAX = 0;
        for (int i = 0; i < diff.length; i++) {
            sum += diff[i];
            if (sum == MAX) {
                count++;
            } else if (MAX < sum) {
                count = 1;
                MAX = sum;
            }
        }
        System.out.println(MAX + " " + count);

    }


    public static void mainMy(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = Integer.valueOf(sc.nextLine());
        int[] st = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::new).toArray();
        int[] et = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::new).toArray();

        TreeMap<Integer, Integer> diff = new TreeMap<>();

        for (int i = 0; i < n; i++) {
            diff.put(st[i], diff.getOrDefault(st[i], 0) + 1);
            diff.put(et[i] + 1, diff.getOrDefault(et[i] + 1, 0) - 1);
        }

        int ans = 0, sum = 0,count = 0;
        for (Map.Entry<Integer, Integer> entry : diff.entrySet()) {
            sum += entry.getValue();
            ans = Math.max(ans, sum);
        }


        // 在数组中操作会比较的好操作
        /*
         下面这种方式非常的巧妙

         因为map 中存储的是 离散化的 st  和et  **点**
         也就是说 st 和 et  在map 中 是不连续的


            这里直接枚举 entry 中的每个点， 作为 流星的 开始起点时间
            如果 此时 达到 max， 则 nextKey - curKey 就是 这个流星区间内的所有满足条件的时间点：

            ** 核心是枚举起始时间点 **

         */
        Map.Entry<Integer, Integer>[] entries = diff.entrySet().toArray(new Map.Entry[0]);

        for (int i = 0; i < entries.length - 1; i++) {
            sum += entries[i].getValue();
            if (sum == ans) {
                count += entries[i + 1].getKey() - entries[i].getKey();
            }
        }
        System.out.println(ans  + " " + count);
    }

    /*
     堆的一个做法, 最大重合的区间的个数, 以及最大重合区间的 点数 ( 有多个最大重合区间  )
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = Integer.valueOf(sc.nextLine());
        int[] st = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::new).toArray();
        int[] et = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::new).toArray();
        int [][]times = new int[n][2];
        for(int i = 0;i < n;i++){
            times[i][0] = st[i];
            times[i][1] = et[i];
        }
        // sort

        Arrays.sort(times,(a,b) -> a[0] - b[0]);

        PriorityQueue<Integer> queue = new PriorityQueue<>();

        int ans = 0, count = 0;

        for(int i = 0;i < n;i++){

            while(!queue.isEmpty() && queue.peek() < times[i][0]){  // 重合的 点 时刻, 也是 合法的区间
                queue.remove();
            }
            queue.add(times[i][1]);

            int temp = queue.size();
            if(ans == temp){
                count += queue.peek() - times[i][0] + 1;
            }else if(ans < temp){
                ans = temp;
                count = queue.peek() - times[i][0] + 1;
            }

        }
        System.out.println(ans + " " + count);
    }



}

